# 前（后） + 中序就能唯一重建一个二叉树，前中序能拿到root节点，通过root节点能够知道左右子树范围，就能唯一的建树
# 整个过程递归的写就可以了

class TreeNode:
    def __init__(self,x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        n = len(preorder)
        pos = dict()

        for i in range(n):
            pos[inorder[i]] = i

        def dfs(preorder, inorder, pl, pr, il, ir):
            if pl > pr:
                return None
            k = pos[preorder[pl]] - il
            root = TreeNode(preorder[pl])
            root.left = dfs(preorder, inorder, pl + 1, pl + k, il, il + k - 1)
            root.right = dfs(preorder, inorder, pl + k + 1, pr, il + k + 1, ir)
            return root

        return dfs(preorder, inorder, 0, n - 1, 0, n - 1)